//
// Created by Mzoro on 2022/4/4.
//
#include "headers.h"

void sort(char *lines[], size_t start, size_t end) {
    if (start >= end) {
        return;
    }

    char *line = lines[start];
    size_t i = start + 1;
    size_t j = end;
    // 假设 line 是最大的
    int isMax = 1;
    // 假设 line 是最小的
    int isMin = 1;
    for (; i < j; ++i) {
        int r1 = strCompare(lines[i], line);
        if (r1 > 0) {
            // lines[i] >= line ,向右移动，从右找
            isMax = 0;
            for (; j > i; --j) {
                int r2 = strCompare(line, lines[j]);
                if (r2 >= 0) {
                    isMin = 0;
                    swap(lines, i, j);
                    break;
                }
            }
        }
    }

    if (isMax) {
        // 说明 line 是最大，要从后向前再次找比line 小的数，与之交接，如果没有，说明后面都是相等的值
        size_t k;
        for (k = end; k > start; --k) {
            int r = strCompare(line, lines[k]);
            if (r > 0) {
                swap(lines, start, k--);
                break;
            }
        }
        sort(lines, start, k);
    } else {
        i--; // 减去for 循环中最后多余的 i++
        if (isMin) {
            // 说明 选中的是最小的数
            sort(lines, i, end);
        } else {
            swap(lines, start, (i - 1));
            sort(lines, start, (i - 1));
            sort(lines, i, end);
        }
    }
}

int strCompare(char *a, char *b) {
    while (*a++ == *b++) {
        if (*a == '\0') {
            break;
        }
    }
    return *(a - 1) >= *(b - 1) ? (*(a - 1) == *(b - 1) ? 0 : 1) : -1;
}

void swap(char *lines[], size_t p1, size_t p2) {
    char *tmp = lines[p1];
    lines[p1] = lines[p2];
    lines[p2] = tmp;
}